1. Field of the Invention
The present invention is related to the field of data encryption. In particular, the present invention is related to a method and apparatus to implement the data encryption standard algorithm.
2. Description of the Related Art
The data encryption standard (DES) specifies a cryptographic algorithm for encrypting and decrypting binary information comprising of 64 bits using a 64-bit key. (Please see the federal information processing standards (FIPS) publication 46-2). The DES specifies both encrypting and decrypting operations, and decrypting is accomplished by using the same key as is used for encrypting but with the schedule for addressing the key bits altered so that decrypting is the reverse of the encrypting process.
A key in the DES consists of 64 binary bits, 56 of these bits are randomly generated and are used by the DES algorithm. The other 8 bits of the key are used for error detection. Users of the encrypted computer data must have the key that was used to encrypt the data in order to decrypt it.
A data block that is to be encrypted is subject to an initial permutation (IP), then to a complex key-dependent computation, and finally to a permutation which is the inverse of the initial permutation (IP−1).
FIG. 1 illustrates a block diagram of a prior art DES implementation 100. As illustrated in FIG. 1, at 105 an input comprising a 64-bit block of data is subject to an IP, to form a permuted input block. The permuted input block 110 is split into a left data block Li-4 120 and a right data block Ri-4 115. Each block Li-4 and Ri-4 comprises 32 data bits. FIG. 1 illustrates 4 DES iterations (181–184) of the 16 DES iterations specified in (FIPS) publication 46-2.
Mathematically, for each DES iteration if the 64 bits of an input block consists of a 32-bit block L followed by a 32-bit block R, then, the input block 105 is LR.
Let K be a block of 48 bits chosen from the 64-bit key. Then the output L′R′ of a single DES iteration with input LR is defined by:L′=R and R′=L(+)f(R, K)  [1]where (+) in equation [1] denotes bit-by-bit addition modulo 2, i.e., an exclusive-or (XOR) function. The next DES iteration uses as input the output from the previous iteration. For the first DES iteration 181, the input block is the left data block Li-4 120 and the right data block Ri-4 115. After the first DES iteration, the output block is:Li-3=Ri-4 and Ri-3=Li-4(+)f(Ri-4,Ki-4)  [2]
While the first 15 iterations have as their output L′R′, the standard specifies that the output of the 16th iteration is R′L′ (also called the pre-output block), which is input into an inverse permutation to generate an encrypted output L′R′. At each iteration, a different block K of key bits, called a sub key, is chosen from the 64-bit key. For details on choosing a sub key block in each DES iteration [1] please refer to FIPS publication 46-2.
The first DES iteration 181 includes a cipher function f(R, K) that comprises expanding Ri-4 115 from 32 bits to 48 bits using expanding function Ei-4 121. Thus, expanding function Ei-4 121 takes a block of 32 Ri-4 bits as input and generates a block of 48 bits as output. The 48-bit expanded Ri-4 output and a first arrangement of 48 sub key bits Ki-4 125 are exclusive-or'd using an exclusive-or function called the first key exclusive-or function 130. The 48 bit output from the first key XOR function 130 is input into a selection function Si-4 135 to obtain a 32 bit selection function output. Selection function Si-4 135 comprises 8 unique selection sub-functions, each of which take 6 bits of the 48 bit output from the first key exclusive-or function 130 as input and yields a 4-bit output. The 32-bit selection function Si-4 135 output is input into a permutation function Pi-4 140 to yield a 32-bit permuted result. A second exclusive-or function, called the first L component XOR function 145, exclusive-ors the 32-bit permuted result with the 32 bit left data block Li-4 120 to yield a right output block Ri-4 155 of the first DES iteration 181. The left output block, Li-3 150 of the first DES iteration comprises the 32-bits of the right data block Ri-4 115. This completes the first DES iteration 181.
The left output block, Li-3 150 and the right output block Ri-3 155 of the first DES iteration 181 serve as input into the second DES iteration 182 to obtain outputs Li-2 161 and Ri-2 162 respectively as described above. Thus, Ri-3 155 is input into expanding function Ei-3 154, and the output from expanding function Ei-3 154 is exclusive-ord with a second key block Ki-3 157 using a second key XOR function 156. The output from the second key XOR function 156 is input into selection function Si-3 158, and the output from selection function Si-3 158 is input into permutation function Pi-3 159 to yield a 32 bit permuted result. The output from permutation function Pi-3 159 is exclusive-ord with Li-3 150 using a second L component XOR function 160 to form output Ri-2 162. The left output block, Li-2 161 of the second DES iteration 182 comprises the 32-bits of the right data block Ri-3 155.
Subsequent DES iterations are repeated multiple times (e.g., at least 16 times) using the output from the previous iteration, with different key blocks. After the multiple iterations, a left and a right pre-output block is obtained. The pre-output blocks are input into IP−1 (not shown) to obtain an encrypted output.
As illustrated in FIG. 1 each cipher function f(R, K) includes two XOR functions (e.g., the first key XOR function 130, and the first L component XOR function 145 of the first DES iteration 181) in the critical path of the calculation. Therefore, for 16 DES iterations, thirty-two XOR functions are in the critical path, and as a result the encryption and/or decryption of data is inefficient.